package club.xiaojiawei.strings;

import java.util.Stack;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/4/22 11:15 PM
 * @question 150. 逆波兰表达式求值
 * @description 根据 逆波兰表示法，求表达式的值。
 * 有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
 * 注意 两个整数之间的除法只保留整数部分。
 * 可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
 */
public class EvalRPN150 {

    public static void main(String[] args) {
        String[] tokens = {"2","1","+","3","*"};
        int result = evalRPN2(tokens);
        System.out.println(result);
    }

    /**
     * 栈
     * @param tokens
     * @return
     */
    public static int evalRPN(String[] tokens) {
        Stack<String> nums = new Stack<>();
        for (String token : tokens) {
            if (judge(token)) {
                nums.push(calc(nums.pop(), nums.pop(), token));
            } else {
                nums.push(token);
            }
        }
        return Integer.parseInt(nums.peek());
    }

    /**
     * String数组
     * @param tokens
     * @return
     */
    public static int evalRPN2(String[] tokens) {
        String[] nums = new String[(tokens.length + 1) >> 1];
        int index = -1;
        for (String token : tokens) {
            if (judge(token)) {
                nums[index - 1] = calc(nums[index--], nums[index], token);
            } else {
                nums[++index] = token;
            }
        }
        return Integer.parseInt(nums[0]);
    }

    /**
     * 民间-递归
     * @param tokens
     * @return
     */
    public static int evalRPN3(String[] tokens) {
        return evo(tokens, new int[]{tokens.length});
    }

    private static int evo(String[] tokens, int[] index){
        switch(tokens[--index[0]]){
            case "+":
                return evo(tokens, index) + evo(tokens, index);
            case "-":
                return -1*evo(tokens, index) + evo(tokens, index);
            case "*":
                return evo(tokens, index) * evo(tokens, index);
            case "/":
                int divisor = evo(tokens, index);
                return evo(tokens, index)/divisor;
            default:
                return Integer.parseInt(tokens[index[0]]);
        }
    }

    /**
     * 计算两数
     * @param n1
     * @param n2
     * @param symbol
     * @return
     */
    public static String calc (String n1, String n2, String symbol){
        return switch (symbol) {
            case "+" -> Integer.toString(Integer.parseInt(n2) + Integer.parseInt(n1));
            case "-" -> Integer.toString(Integer.parseInt(n2) - Integer.parseInt(n1));
            case "/" -> Integer.toString(Integer.parseInt(n2) / Integer.parseInt(n1));
            default -> Integer.toString(Integer.parseInt(n2) * Integer.parseInt(n1));
        };
    }

    /**
     * 判断是符号还是数字
     * @param s
     * @return
     */
    public static boolean judge(String s){
        return "+".equals(s) || "-".equals(s) || "/".equals(s) || "*".equals(s);
    }
}
